`
https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minCost = function (grid) {
  // 每个格子当成一个节点，同方向则边的权重为 0 ，否则为 1
  // 这样便能转换成一个加权有向图，使用 Dijkstra 算法求解即可
  const m = grid.length, n = grid[0].length
  // datastructures-js Heap
  const pq = new Heap((a, b) => a.costFromStart - b.costFromStart)
  const distTo = Array.from({ length: m }, () => new Array(n).fill(Infinity))
  distTo[0][0] = 0
  pq.push(new State(0, 0, 0))
  // 方向语义化
  const DIREC = { RIGHT: 1, LEFT: 2, DOWN: 3, UP: 4 }
  const allNext = [
    [1, 0, DIREC.DOWN],
    [-1, 0, DIREC.UP],
    [0, 1, DIREC.RIGHT],
    [0, -1, DIREC.LEFT]
  ]

  const isValid = (x, y) => {
    return x >= 0 && y >= 0 && x < m && y < n
  }

  while (!pq.isEmpty()) {
    const curNode = pq.pop()
    const curX = curNode.x
    const curY = curNode.y
    const curCostFromStart = curNode.costFromStart
    // 拿到当前节点的方向
    const curDir = grid[curX][curY]

    // 到达终点直接返回法案
    if (curX === m - 1 && curY === n - 1) return curCostFromStart

    for (const [x, y, dir] of allNext) {
      const nextX = curX + x
      const nextY = curY + y
      if (!isValid(nextX, nextY)) continue
      // 同方向不需要花费，否则花费 1 cost
      const nextCostFromStart = curCostFromStart + (curDir === dir ? 0 : 1)
      if (nextCostFromStart < distTo[nextX][nextY]) {
        distTo[nextX][nextY] = nextCostFromStart
        pq.push(new State(nextX, nextY, nextCostFromStart))
      }
    }
  }
};

class State {
  constructor(x, y, costFromStart) {
    this.x = x
    this.y = y
    this.costFromStart = costFromStart
  }
}